home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 7 / Night Owl Shareware (NOPV7)(Night Owl Publisher Inc.)(1992).bin / 038a / bash1_12.arj / BASH1-12.TAR / bash-1.12 / hash.c < prev    next >
C/C++ Source or Header  |  1991-07-07  |  6KB  |  255 lines
  1. /* Hash.c -- Where hashing for bash is done. */
  2.  
  3. /* Copyright (C) 1987, 1989, 1991 Free Software Foundation, Inc.
  4.  
  5. This file is part of GNU Bash, the Bourne Again SHell.
  6.  
  7. Bash is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 1, or (at your option) any later
  10. version.
  11.  
  12. Bash is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with Bash; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21. /* There appears to be library functions for this stuff, but it seems like
  22.    a lot of overhead, so I just implemented this hashing stuff on my own. */
  23.  
  24. #include "shell.h"
  25. #include "hash.h"
  26.  
  27. HASH_TABLE *hashed_filenames;
  28.  
  29. #define FILENAME_HASH_BUCKETS 107
  30.  
  31. /* Create the hash table for filenames that we use in the shell. */
  32. initialize_hashed_filenames ()
  33. {
  34.   hashed_filenames = make_hash_table (FILENAME_HASH_BUCKETS);
  35. }
  36.  
  37. /* Make a new hash table with BUCKETS number of buckets.  Initialize
  38.    each slot in the table to NULL. */
  39. HASH_TABLE *
  40. make_hash_table (buckets)
  41.      int buckets;
  42. {
  43.   HASH_TABLE *new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
  44.  
  45.   if (!buckets)
  46.     buckets = DEFAULT_HASH_BUCKETS;
  47.  
  48.   new_table->bucket_array =
  49.     (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
  50.   new_table->nbuckets = buckets;
  51.   new_table->nentries = 0;
  52.   initialize_hash_table (new_table);
  53.   return (new_table);
  54. }
  55.  
  56. /* Zero the buckets in TABLE. */
  57. initialize_hash_table (table)
  58.      HASH_TABLE *table;
  59. {
  60.   register int i;
  61.   for (i = 0; i < table->nbuckets; i++)
  62.     table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
  63. }
  64.  
  65. /* Return the location of the bucket which should contain the data
  66.    for STRING.  TABLE is a pointer to a HASH_TABLE. */
  67. hash_string (string, table)
  68.      char *string;
  69.      HASH_TABLE *table;
  70. {
  71.   register unsigned int i = 0;
  72.  
  73.   while (*string) i += *string++;
  74.   i %= table->nbuckets;
  75.   return (i);
  76. }
  77.  
  78. /* Return a pointer to the hashed item, or NULL if the item
  79.    can't be found. */
  80. BUCKET_CONTENTS *
  81. find_hash_item (string, table)
  82.      char *string;
  83.      HASH_TABLE *table;
  84. {
  85.   BUCKET_CONTENTS *list;
  86.  
  87.   list = table->bucket_array[hash_string (string, table)];
  88.  
  89.   while (list)
  90.     {
  91.       if (STREQ (list->key, string))
  92.     {
  93.       list->times_found++;
  94.       return (list);
  95.     }
  96.       else list = list->next;
  97.     }
  98.   return (BUCKET_CONTENTS *)NULL;
  99. }
  100.  
  101. /* Remove the item specified by STRING from the hash table TABLE.
  102.    The item removed is returned, so you can free its contents.  If
  103.    the item isn't in this table NULL is returned. */
  104. BUCKET_CONTENTS *
  105. remove_hash_item (string, table)
  106.      char *string;
  107.      HASH_TABLE *table;
  108. {
  109.   int the_bucket = hash_string (string, table);
  110.   BUCKET_CONTENTS *prev = (BUCKET_CONTENTS *)NULL;
  111.   BUCKET_CONTENTS *temp = table->bucket_array[the_bucket];
  112.  
  113.   while (temp)
  114.     {
  115.       if (strcmp (temp->key, string) == 0)
  116.     {
  117.       if (prev)
  118.         prev->next = temp->next;
  119.       else
  120.         table->bucket_array[the_bucket] = temp->next;
  121.  
  122.       table->nentries--;
  123.       return (temp);
  124.     }
  125.       prev = temp;
  126.       temp = temp->next;
  127.     }
  128.   return ((BUCKET_CONTENTS *) NULL);
  129. }
  130.  
  131. /* Create an entry for STRING, in TABLE.  If the entry already
  132.    exists, then return it. */
  133. BUCKET_CONTENTS *
  134. add_hash_item (string, table)
  135.      char *string;
  136.      HASH_TABLE *table;
  137. {
  138.   BUCKET_CONTENTS *item;
  139.  
  140.   if (!(item = find_hash_item (string, table)))
  141.     {
  142.       int bucket = hash_string (string, table);
  143.       item = table->bucket_array[bucket];
  144.  
  145.       while (item && item->next) item = item->next;
  146.       if (item)
  147.     {
  148.       item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
  149.       item = item->next;
  150.     }
  151.       else
  152.     {
  153.       table->bucket_array[bucket] =
  154.         (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
  155.       item = table->bucket_array[bucket];
  156.     }
  157.  
  158.       item->data = (char *)NULL;
  159.       item->next = (BUCKET_CONTENTS *)NULL;
  160.       item->key = string;
  161.       table->nentries++;
  162.       item->times_found = 0;
  163.     }
  164.  
  165.   return (item);
  166. }
  167.  
  168. /* Return the bucket_contents list of bucket BUCKET in TABLE.  If
  169.    TABLE doesn't have BUCKET buckets, return NULL. */
  170. BUCKET_CONTENTS *
  171. get_hash_bucket (bucket, table)
  172.      int bucket;
  173.      HASH_TABLE *table;
  174. {
  175.   if (bucket < table->nbuckets)
  176.     return (table->bucket_array[bucket]);
  177.   else
  178.     return (BUCKET_CONTENTS *)NULL;
  179. }
  180.  
  181. #ifdef TEST_HASHING
  182.  
  183. #undef NULL
  184. #include <stdio.h>
  185.  
  186. HASH_TABLE *table;
  187. #define NBUCKETS 107
  188.  
  189. xmalloc (bytes)
  190.      int bytes;
  191. {
  192.   char *result = (char *)malloc (bytes);
  193.   if (!result)
  194.     {
  195.       fprintf (stderr, "Out of memory!");
  196.       abort ();
  197.     }
  198.   return ((int)result);
  199. }
  200.  
  201. main ()
  202. {
  203.   char string[256];
  204.   int count = 0;
  205.   BUCKET_CONTENTS *tt;
  206.  
  207.   table = make_hash_table (NBUCKETS);
  208.   
  209.   printf ("Enter some data to be hashed, a word at a time.\n\
  210. Type a blank line when done:\n\n");
  211.  
  212.   for (;;)
  213.     {
  214.       char *temp_string = savestring (gets (string));
  215.       if (!*string) break;
  216.       tt = add_hash_item (temp_string, table);
  217.       if (tt->times_found)
  218.     {
  219.       printf ("\nYou have already added that item\n");
  220.       free (temp_string);
  221.     }
  222.       else
  223.     {
  224.       count++;
  225.     }
  226.     }
  227.   
  228.   printf ("\nYou have entered %d (%d) items.  The items are:\n\n",
  229.       table->nentries, count);
  230.  
  231.   for (count = 0; count < table->nbuckets; count++)
  232.     {
  233.       register BUCKET_CONTENTS *list = get_hash_bucket (count, table);
  234.     
  235.       if (list)
  236.     {
  237.       printf ("%3d slot: ", count);
  238.       while (list)
  239.         {
  240.           printf ("%s\n         ", list->key);
  241.           list = list->next;
  242.         }
  243.       printf ("\n");
  244.     }
  245.     }
  246. }
  247.  
  248. #endif /* TEST_HASHING */
  249.  
  250. /*
  251.  * Local variables:
  252.  * compile-command: "gcc -g -DTEST_HASHING -o hash hash.c"
  253.  * end:
  254.  */
  255.